Floyd's Rabbit and Turtle Algorithm

AI Generated

Floyd's Cycle-Finding Algorithm is a pointer algorithm used to detect a cycle in a linked list (or any iterated function) using only constant space () and linear time ().

Why It Works (Intuition)

Imagine two runners, a Tortoise and a Hare, on a race track that includes a loop.

• The Tortoise runs slowly (1 step at a time).
• The Hare runs fast (2 steps at a time).

If the track is a straight line, the Hare will simply reach the finish line first and never meet the Tortoise again. However, if there is a loop (cycle), the Hare will enter the loop, run around it, and eventually "lap" the Tortoise from behind.

Mathematically, the relative speed difference means the gap between them decreases by 1 step every iteration once they are both inside the cycle. Eventually, they are guaranteed to land on the same node.

---

Algorithm Pseudocode (Cycle Detection)

To detect if a cycle exists, we initialize both pointers at the head.

function detectCycle(head):
    slow = head
    fast = head

    while fast is not NULL and fast.next is not NULL:
        slow = slow.next          # Move 1 step
        fast = fast.next.next     # Move 2 steps

        if slow == fast:
            return True           # Cycle detected (Collision point)

    return False                  # End of list reached, no cycle

---

Finding the Start of the Cycle

Once a cycle is detected (the Hare and Tortoise meet), you can find exactly where the cycle begins using the following steps:

1. Keep the Hare (or one pointer) at the meeting point.
2. Reset the Tortoise (or the other pointer) back to the Head of the list.
3. Move both pointers one step at a time.
4. The node where they meet again is the start of the cycle.

Pseudocode (Find Start Node)

function findCycleStart(head):
    slow = head
    fast = head
    collision = False

    # Step 1: Detect Cycle
    while fast is not NULL and fast.next is not NULL:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            collision = True
            break
    
    if not collision:
        return NULL # No cycle

    # Step 2: Find Start
    slow = head             # Reset slow to head
    while slow != fast:     # Move both 1 step until they meet
        slow = slow.next
        fast = fast.next
    
    return slow             # This is the start of the cycle